package com.tian.dataStructure.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode heroNode1=new HeroNode(1,"hello","world");
        HeroNode heroNode2=new HeroNode(2,"田","小田");
        HeroNode heroNode3=new HeroNode(3,"亚","ya");
        HeroNode heroNode4=new HeroNode(4,"康","kang");

        SingleLinkedList linkedList=new SingleLinkedList();
        linkedList.add(heroNode1);
        linkedList.add(heroNode2);
        linkedList.add(heroNode3);
        linkedList.add(heroNode4);

//        linkedList.addByOrder(heroNode1);
//        linkedList.addByOrder(heroNode3);
//        linkedList.addByOrder(heroNode2);
//        linkedList.addByOrder(heroNode4);
        linkedList.list();

//        System.out.println("反转单链表后");
//        reversetList(linkedList.getHead());
//        linkedList.list();

        System.out.println("测试逆序打印单链表 没有改变链表的本身结构~~~");
        reversePrint(linkedList.getHead());


/*
        //测试修改节点的代码
        HeroNode newHeroNode=new HeroNode(2,"田小甜","天天向上");
        linkedList.update(newHeroNode);
        System.out.println("修改后的情况__");
        linkedList.list();

        //测试删除节点
        linkedList.del(1);
        linkedList.del(4);
        System.out.println("删除后的链表情况~~~");
        linkedList.list();

        //测试一下 求单链表中有效节点的个数
        System.out.println("有效的节点个数="+getLength(linkedList.getHead()));

        //测试一下是否得到了倒数第K个节点
        HeroNode res = findLastIndexNode(linkedList.getHead(), 2);
        System.out.println("res:"+res);*/
    }


    //方法：获取到单链表的节点的个数（如果是带头节点的链表，不统计头节点）

    /**
     *
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode head){
        int length=0;
        if (head.next==null){
            return 0;
        }
        HeroNode cur=head.next;
        while (cur!=null){
            length++;
            cur=cur.next;
        }
        return length;
    }

    //查找单链表中的倒数第K个节点（新浪面试题）
    //思路
    //1.编写一个方法，接收head节点，同时接收一个index
    //2.index表示是倒数第index个节点
    //3.先把链表从头到尾遍历，得到链表的总的长度getLength
    //4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
    //5.如果找到了，则返回该节点，否则返回null
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        if (head.next==null){
            return null;
        }
        int size = getLength(head);

        if (index<=0 || index>size){
            return null;
        }
        HeroNode cur=head.next;
        for (int i=0;i<size-index;i++){
            cur=cur.next;
        }
        return cur;
    }

    //将链表反转
    public static void reversetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next==null || head.next.next ==null){
            return;
        }
        //定义一个辅助的指针（变量),帮助我们遍历原来的链表
        HeroNode cur=head.next;
        HeroNode next=null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead=new HeroNode(0,"","");

        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur!=null){
            next=cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next=reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next=cur;//将cur连接到新的链表中
            cur=next;//让cur后移
        }
        //将head.next指向reverseHead.next，实现单链表的反转
        head.next=reverseHead.next;
    }

    //将链表逆序打印
    //思路：利用栈，将各个节点压入到栈中，然后利用栈的先进后出的特点，实现逆序打印
    public static void reversePrint(HeroNode head){
        if (head.next==null){
            return; //空链表，不能打印
        }
        //创建一个栈，将各个节点压入栈
        Stack<HeroNode> stack=new Stack<>();
        HeroNode cur=head.next;
        //将链表的所有节点压入栈
        while (cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }

}




class SingleLinkedList{
    //先初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head=new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1.找到当前链表的最后节点
    //2。将最后这个节点的next 指向新的节点
    public void add(HeroNode heroNode){
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=heroNode;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此通过一个辅助指针（变量）来帮助找到添加的位置
        //因为是单链表，所以temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp=head;
        boolean flag=false;//flag标志添加的编号是否存在，默认为false
        while (true){
            if (temp.next==null){//说明temp已经在链表的最后
                break;
            }
            if (temp.next.no>heroNode.no){//注意：位置找到，就在temp的后面插入
                break;
            }
            if (temp.next.no==heroNode.no){//说明希望添加的heroNode的No已经存在
                flag=true; //说明编号存在
                break;
            }
            temp=temp.next;//后移，遍历当前链表
        }
        if (flag){ //不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);
        }else {
            //插入到链表中，temp的后面
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }

    //修改节点的信息，根据no编号来修改，即no编号不能改
    public void update(HeroNode newHeroNode){
        //判断是否空
        if (head.next==null){
            System.out.println("链表为空~~");
            return;
        }
        boolean flag=false; //表示是否找到该节点
        HeroNode temp=head.next;
        while (true){
            if (temp==null){
                break;//已经遍历完链表
            }
            if (temp.no==newHeroNode.no){
                //找到
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.name=newHeroNode.name;
            temp.nickName=newHeroNode.nickName;
        }else {
            System.out.printf("没有找到编号 %d 的节点，不能修改\n",newHeroNode.no);
        }
    }

    //删除节点
    //1. head不能动，因此需要一个temp辅助节点找到待删除节点的前一个节点
    //2.在比较时，temp.next.no和需要删除节点的no进行比较
    public void del(int no){
        boolean flag=false; //标志是否找到待删除节点
        HeroNode temp=head;
        while (true){
            if (temp.next==null){ //已经到链表的最后
                break;
            }
            if (temp.next.no==no){
                //找到待删除的节点的前一个节点temp
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            //可以删除
            temp.next=temp.next.next;
        }else {
            System.out.printf("要删除的 %d 节点不存在\n",no);
        }
    }

    public void list(){
        //判断链表是否为空
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
        HeroNode temp=head.next;
        while (true){
            //判断是否到链表最后
            if (temp==null){
                break;
            }
            System.out.println(temp);
            temp=temp.next;
        }
    }



}

class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}